package 中等.贪心思想;

/**
 * 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
 * <p>
 * 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/increasing-triplet-subsequence
 */
public class 递增的三元子序列_334 {

    public static void main(String[] args) {

        int[] nums = {20, 100, 10, 12, 5, 13};
        System.out.println(efficientIncreasingTriplet(nums));

    }

    /**
     * @param nums
     * @return
     */
    public static boolean increasingTriplet(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            //找两个符号条件的元素
            int firstNum = nums[i];
            Integer twoNum = null;
            for (int j = i + 1; j < nums.length; j++) {
                if (twoNum != null) {  //第二个数字
                    if (nums[j] > twoNum) {
                        return true;
                    }
                }
                if (firstNum < nums[j]) {
                    if (twoNum != null) {  //贪心的选择比第一个数字大的数字中最小的数字
                        twoNum = Math.min(twoNum, nums[j]);
                    }
                    twoNum = nums[j];
                }
            }
        }
        return false;
    }

    /**
     * 贪心思想
     * 站在第二个元素考虑，我只要比我之前元素中最小的元素大就可以
     * 站在第三个元素考虑，我只要比第二个元素大就可以，而且
     * 第二个元素的初始值是最大值，如果第二个元素被赋值，那么它必然前面有一个比它小的元素
     *
     * @param nums
     * @return
     */
    public static boolean increasingTriplet2(int[] nums) {
        int firstNum = nums[0];
        int twoNum = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int curNum = nums[i];
            firstNum = Math.min(firstNum, curNum);
            if (curNum > twoNum) {
                return true;
            }
            if (curNum > firstNum) {
                twoNum = Math.min(twoNum, curNum);
            }
        }
        return false;
    }

    /**
     * 代码优化
     * 当前元素是否大于第二个元素
     * 如果大于，就是one<two<cur，直接成功，如果小于
     * 判断是否大于第一个元素
     * 如果大于第一个元素，就是one<cur<two的条件，那么第二个元素two=cur，贪心选择比较小的第二个元素
     * 如果小于第一个元素，就是cur<one，那么one=cur，贪心的选择比较小的第一个元素
     *
     * @param nums
     * @return
     */
    public static boolean efficientIncreasingTriplet(int[] nums) {
        int firstNum = nums[0];
        int twoNum = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int curNum = nums[i];
            if (curNum > twoNum) {  //第二个元素的初始值是最大值，如果第二个元素被赋值，那么它必然前面有一个比它小的元素
                return true;
            } else if (curNum > firstNum) {   //当前元素如果比第二个元素大，那么就直接成功了，那么这里一定是比第二个元素小，可以直接赋值！！！
                twoNum = curNum;
            } else {  //当前元素比第一个元素大，将会赋给第二个元素，所以这里一定比第一个元素小，可以直接赋值！！！
                firstNum = curNum;
            }
        }
        return false;
    }

}
